package com.tgy.algorithm._经典题目01;


import com.tgy.algorithm.base.other.BiTreeNode;

/**
 * 求完全二叉树节点的个数
 * 要求时间复杂度低于O(N)
 */
public class _029_计算完成二叉树节点 {

    public static BiTreeNode generalBiTreeNode() {

        /**
         * 2 ^ 2 - 1
         * 2^3 - 1
         *               9
         *           6          12
         *        3     7    10    13
         *     1    1 1
         *
         * 2^ 1 - 1
         *        8
         *      1    2
         *   2    1
         *
         *              9
         *          6      12
         *       3   7   10  13
         *     1  1 3
         */
        BiTreeNode root = new BiTreeNode(9);
        root.left = new BiTreeNode(6);
        root.right = new BiTreeNode(12);
        root.left.left = new BiTreeNode(3);
        root.left.right = new BiTreeNode(7);
        root.right.left = new BiTreeNode(10);
        root.right.right = new BiTreeNode(13);

        root.left.left.left = new BiTreeNode(1);
        root.left.left.right = new BiTreeNode(2);
        root.left.right.left = new BiTreeNode(3);
        root.left.right.right = new BiTreeNode(4);

        return root;
    }

    public static int cbfNodes(BiTreeNode root) {

        if (root == null) {
            return 0;
        }

        int treeHeight = getLevel(root);
        return doCbfNodes(root,treeHeight,1);
    }

    public static int doCbfNodes(BiTreeNode root,int treeHeight, int level) {

        if (root == null) {
            return 0;
        }

        BiTreeNode right = root.right;

        int subTreeHeight;

        if (right != null) {
            subTreeHeight = getLevel(right);
        }else {
            return root.left == null ? 1:2;
        }

        if (treeHeight == ( subTreeHeight + level)) {
           // 左边的二叉树是满的
           int leftNodes = doCbfNodes(root.right,treeHeight,level+1);
           return leftNodes + (1  << subTreeHeight);
       }else {
           // 右边的二叉树是满的
           int rightNodes = doCbfNodes(root.left,treeHeight,level+1);
           return rightNodes + (1 << subTreeHeight);
       }
    }

    public static int getLevel(BiTreeNode root) {

        int level = 0;
        BiTreeNode node = root;
        while (node != null) {
            level++;
            node = node.left;
        }

        return level;
    }


    public static void main(String[] args) {
        BiTreeNode root = generalBiTreeNode();
        int nodes = cbfNodes(root);
        System.out.println(nodes);
    }
}
